#define _CRT_SECURE_NO_WARNINGS
class Solution {
public:
    int countSubstrings(string s) {
        int n = s.size();
        vector<vector<bool>> dp(n, vector<bool>(n, false));
        for (int i = n - 1; i >= 0; i--)
        {
            for (int j = i; j < n; j++)
            {
                if (i == j)
                    dp[i][j] = true;
                else if (i + 1 == j && s[i] == s[j])
                    dp[i][j] = true;
                else if (s[i] == s[j])
                    dp[i][j] = dp[i + 1][j - 1];
            }
        }
        int ret = 0;
        for (int i = 0; i < n; i++)
        {
            for (int j = i; j < n; j++)
            {

                if (dp[i][j])
                {
                    //cout<<i<<":"<<j<<endl;
                    ret++;

                }
            }
        }
        return ret;
    }
};

class Solution {
public:
    string longestPalindrome(string s) {
        int n = s.size();
        vector<vector<bool>> dp(n, vector<bool>(n, false));
        //int ret = 1;
        int begin = 0;
        int len = 1;
        for (int i = n - 1; i >= 0; i--)
        {
            for (int j = i; j < n; j++)
            {
                if (i == j)
                    dp[i][j] = true;
                else if (i + 1 == j && s[i] == s[j])
                {
                    dp[i][j] = true;
                }
                else if (s[i] == s[j])
                {
                    dp[i][j] = dp[i + 1][j - 1];
                }
                cout << i << ":" << j << " " << dp[i][j] << endl;
                if (dp[i][j])
                {
                    if (j - i + 1 > len)
                    {
                        begin = i;
                        //cout<<begin<<endl;
                        len = j - i + 1;
                        //ret = i-j+1;
                    }
                }
            }
        }
        //cout<<begin<<" "<<len<<endl;
        return s.substr(begin, len);
    }
};
